package daily_exercise;

import java.util.*;

public class Demo4 {



    // 521. 最长特殊序列 Ⅰ
    public int findLUSlength(String a, String b) {
        int n = a.length(), m = b.length();
        if (n != m) return Math.max(n, m);

        int[] hash1 = new int[26], hash2 = new int[26];
        for (char ch : a.toCharArray()) {
            hash1[ch - 'a']++;
        }
        for (char ch : b.toCharArray()) {
            hash2[ch - 'a']++;
        }

        for (int i = 0; i < 26; i++) {
            if (hash1[i] != hash2[i]) return n;
        }

        for (int i = 0; i < n; i++) {
            if (a.charAt(i) != b.charAt(i)) return n - i;
        }
        return -1;
    }



    // 522. 最长特殊序列 II
    public int findLUSlength(String[] strs) {
        int res = -1, n = strs.length;
        // 枚举
        for (int i = 0; i < n; i++) {
            int j = 0;
            // 判断子序列: strs[i] 是否为 strs[j] 的子序列
            for (; j < n; j++) {
                if (i == j) continue;

                int cur1 = 0, cur2 = 0, len1 = strs[i].length(), len2 = strs[j].length();
                while (cur1 < len1 && cur2 < len2) {
                    for (; cur1 < len1 && cur2 < len2 && strs[i].charAt(cur1) == strs[j].charAt(cur2); cur1++, cur2++);
                    cur2++;
                }
                if (cur1 == len1) break;
            }
            if (j == n && strs[i].length() > res) res =  strs[i].length();
        }
        return res;
    }



    // 2288. 价格减免
    public String discountPrices(String sentence, int discount) {
        StringBuilder res = new StringBuilder();
        for (int i = 0, n = sentence.length(); i < n; ) {
            char ch = sentence.charAt(i);
            if (ch != '$') {
                res.append(ch);
                i++;
            } else {
                res.append('$');
                int j = i + 1;
                while (j < n && sentence.charAt(j) != ' ') j++;
                String s = sentence.substring(i + 1, j);
                // $必须为第一个字符或前面为空格才代表价格
                if ((i == 0 || sentence.charAt(i - 1) == ' ') && check(s)) {
                    double num = Long.parseLong(s) * (1.0 - discount / 100.0);
                    s = String.format("%.2f", num);
                }
                res.append(s);
                i = j;
            }
        }
        return res.toString();
    }
    private boolean check(String s) {
        if (s.equals("")) return false;
        for (char ch : s.toCharArray()) {
            if (ch < '0' || ch > '9') return false;
        }
        return true;
    }



    // 2748. 美丽下标对的数目
    public int countBeautifulPairs(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int num1 = Integer.toString(nums[i]).charAt(0) - '0';
                int num2 = nums[j] % 10;
                if (gcd(num1, num2) == 1) res++;
            }
        }
        return res;
    }
    private int gcd(int x, int y) {
        int tmp = 0;
        while (x % y != 0) {
            tmp = x % y;
            x = y;
            y = tmp;
        }
        return y;
    }



    // LCP 61. 气温变化趋势
    public int temperatureTrend(int[] temperatureA, int[] temperatureB) {
        int n = temperatureA.length;
        int left = 0, right = 1;
        int res = 0;
        while (right < n) {
            int diff1 = temperatureA[right] - temperatureA[right - 1];
            int diff2 = temperatureB[right] - temperatureB[right - 1];
            if ((diff1 == 0 && diff2 == 0) || diff1 * diff2 > 0) {
                res = Math.max(res, right - left);
            } else {
                left = right;
            }
            right++;
        }
        return res;
    }



    // 520. 检测大写字母
    public boolean detectCapitalUse(String word) {
        boolean up = false, low = false;
        for (int i = 1, n = word.length(); i < n; i++) {
            char ch = word.charAt(i);
            if (ch >= 'A' && ch <= 'Z') up = true;
            else low = true;
        }

        char ch = word.charAt(0);
        if (ch >= 'A' && ch <= 'Z') {
            if (up && low) return false;
            return true;
        }
        if (!up) return true;
        return false;
    }



    // 2065. 最大化一张图中的路径价值
    // 记录各边的出度和所花费时间
    private Map<Integer, List<int[]>> outs;
    // 记录 dfs 过程中每个结点的遍历次数,当 vis[i] == 0 时,才计入价值
    private int[] vis;
    private int res;

    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.length;
        vis = new int[n];
        outs = new HashMap<>();
        for (int[] e : edges) {
            if (!outs.containsKey(e[0])) {
                outs.put(e[0], new ArrayList<>());
            }
            if (!outs.containsKey(e[1])) {
                outs.put(e[1], new ArrayList<>());
            }
            outs.get(e[0]).add(new int[]{e[1], e[2]});
            outs.get(e[1]).add(new int[]{e[0], e[2]});
        }

        dfs(0, 0, 0, maxTime, values);
        return res;
    }
    private void dfs(int cur, int sum, int time, int maxTime, int[] values) {
        // 统计价值
        if (vis[cur]++ == 0) sum += values[cur];
        if (cur == 0) res = Math.max(res, sum);

        if (time >= maxTime) {
            if (time == maxTime) vis[cur]--;
            return;
        }

        for (int[] arr : outs.getOrDefault(cur, new ArrayList<>())) {
            // 剪枝
            if (time + arr[1] > maxTime) continue;
            dfs(arr[0], sum, time + arr[1], maxTime, values);
        }
        if (--vis[cur] == 0) sum -= values[cur];
    }



    // 494. 目标和
    public int findTargetSumWays(int[] nums, int target) {
        // 设所有正数之和为 a,所有负数之和为b.
        // 则所有整数之和 sum + target == 2a
        int sum = 0, n = nums.length;
        for (int x : nums) sum += x;
        if ((sum + target) % 2 == 1) return 0;
        int aim = (sum + target) / 2;
        if (aim < 0) return 0;

        // dp[i][j]:从前 i 个数中选取若干个数,使它们的和恰好为 j 共有多少种构造方式
        int[] dp = new int[aim + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= nums[i - 1]; j--) {
                dp[j] += dp[j - nums[i - 1]];
            }
        }
        return dp[aim];
    }



    // 3115. 质数的最大距离
    public int maximumPrimeDifference(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left < n && !isPrimeNum(nums[left])) left++;
        while (right >= left && !isPrimeNum(nums[right])) right--;
        return right - left;
    }
    private boolean isPrimeNum(int num) {
        if (num == 1) return false;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }



    // 3099. 哈沙德数
    public int sumOfTheDigitsOfHarshadNumber(int x) {
        int sum = 0;
        for (int num = x; num != 0; num /= 10) {
            sum += num % 10;
        }
        if (x % sum == 0) return sum;
        return -1;
    }


    // 3033. 修改矩阵
    public int[][] modifiedMatrix(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int[] colsMax = new int[m];

        int[][] res = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res[i][j] = matrix[i][j];
                if (matrix[i][j] > colsMax[j]) colsMax[j] = matrix[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (res[i][j] == -1) {
                    res[i][j] = colsMax[j];
                }
            }
        }

        return res;
    }



    // 3101. 交替子数组计数
    public long countAlternatingSubarrays(int[] nums) {
        // dp[i]: 以 i 位置为结尾的所有子数组中,交替子数组的数量
        int n = nums.length;
        int a = 1, b = 0;

        long res = 1;
        for (int i = 1; i < n; i++) {
            b = 1;
            if (nums[i] != nums[i - 1]) {
                b += a;
            }
            res += b;
            a = b;
        }
        return res;
    }



    // 1958. 检查操作是否合法
    private char[][] arr;
    private char color;

    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        this.arr = board;
        this.color = color;

        // 从(rMove,cMove)开始,往上下左右和斜对角的方向寻找颜色为 color 的格子
        if (search(rMove, cMove, -1, 0) >= 3) return true;
        if (search(rMove, cMove, 1, 0) >= 3) return true;
        if (search(rMove, cMove, 0, -1) >= 3) return true;
        if (search(rMove, cMove, 0, 1) >= 3) return true;
        if (search(rMove, cMove, -1, -1) >= 3) return true;
        if (search(rMove, cMove, -1, 1) >= 3) return true;
        if (search(rMove, cMove, 1, -1) >= 3) return true;
        if (search(rMove, cMove, 1, 1) >= 3) return true;
        return false;
    }
    private int search(int x, int y, int dx, int dy) {
        x += dx;
        y += dy;
        int res = 1;

        for (; x >= 0 && x < 8 && y >= 0 && y < 8; x += dx, y += dy) {
            if (arr[x][y] == '.') return -1;
            res++;
            if (arr[x][y] == color) return res;
        }
        return -1;
    }



    // 724. 寻找数组的中心下标
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int rightSum = 0;
        for (int i = n - 1; i > 0; i--) {
            rightSum += nums[i];
        }

        int leftSum = 0;
        for (int i = 0; i < n; i++) {
            if (leftSum == rightSum) return i;
            leftSum += nums[i];
            if (i < n - 1) rightSum -= nums[i + 1];
        }
        return -1;
    }




    // 2974. 最小数字游戏
    public int[] numberGame(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n; i += 2) {
            int tmp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = tmp;
        }
        return nums;
    }



    // 3011. 判断一个数组是否可以变为有序
    public boolean canSortArray(int[] nums) {
        // 1. 将数组按从小到大排序
        int n = nums.length;
        int[] tmpArr = new int[n];
        for (int i = 0; i < n; i++) {
            tmpArr[i] = nums[i];
        }
        Arrays.sort(tmpArr);

        // 2. 计算数组中每个数二进制下位为 1 的数目
        int[] oneCount = new int[257];
        for (int x : nums) {
            if (oneCount[x] != 0) continue;

            int count = 0;
            for (int i = x; i != 0; ) {
                count++;
                i &= (i - 1);
            }
            oneCount[x] = count;
        }

        // 3. 根据排序后的数组,遍历原来的数组,查看本次要操作的数字是否能够交换到要排序的位置
        for (int i = 0; i < n - 1; i++) {
            int index = i;
            while (index < n && nums[index] != tmpArr[i]) index++;
            // 查看前面的数字是否 1的位数 都一样
            for (int j = index - 1; j >= i; j--) {
                if (oneCount[nums[j]] != oneCount[nums[index]]) return false;
            }
            // 交换元素
            int tmp = nums[i];
            nums[i] = nums[index];
            nums[index] = tmp;
        }
        return true;
    }



    // 2956. 找到两个数组中的公共元素
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        boolean[] vis1 = new boolean[101];
        boolean[] vis2 = new boolean[101];
        for (int x : nums1) {
            vis1[x] = true;
        }
        for (int x : nums2) {
            vis2[x] = true;
        }

        int[] res = new int[2];
        for (int x : nums1) {
            if (vis2[x]) res[0]++;
        }
        for (int x : nums2) {
            if (vis1[x]) res[1]++;
        }
        return res;
    }




    // 3112. 访问消失节点的最少时间
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        // 1. 记录各边的出度
        Map<Integer, List<int[]>> hash = new HashMap<>();
        for (int[] e : edges) {
            int e0 = e[0], e1 = e[1], time = e[2];
            if (!hash.containsKey(e0))
                hash.put(e0, new ArrayList<>());
            if (!hash.containsKey(e1))
                hash.put(e1, new ArrayList<>());
            hash.get(e0).add(new int[] { e1, time });
            hash.get(e1).add(new int[] { e0, time });
        }

        // 2. 广度优先遍历
        // int[]: 节点编号-消耗时间
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        answer[0] = 0;

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { 0, 0 });
        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int index = arr[0], time = arr[1];
            // 之前已经更新过
            if (time > answer[index]) continue;

            for (int[] tmp : hash.getOrDefault(index, new ArrayList<>())) {
                int nextTime = time + tmp[1];
                int nextIndex = tmp[0];
                // 入队列条件:该节点还没消失 1)此时消耗时间比之前到达时间小 2)从未到达该节点
                if (nextTime < disappear[nextIndex] && (nextTime < answer[nextIndex] || answer[nextIndex] == -1)) {
                    // 在此处更新结果,可以避免后续重复加入同一结点
                    answer[nextIndex] = nextTime;
                    q.offer(new int[] { nextIndex, nextTime });
                }
            }
        }
        return answer;
    }
}
